export namespace NumNet {
  /** 单链表节点
   *
   */
  export class ListNode {
    val: number;
    next: ListNode | null;
    constructor(val?: number, next?: ListNode | null) {
      this.val = val === undefined ? 0 : val;
      this.next = next === undefined ? null : next;
    }
  }

  /** 链表
   *
   */
  export class LinkedList {
    private size: number;
    private head: ListNode | null;
    private tail: ListNode | null;
    constructor() {
      this.size = 0;
      this.head = null;
      this.tail = null;
    }

    /** 获取链表中第 index个节点的值
     * O(index)
     * @param index 索引值
     * @returns
     */
    get(index: number) {
      if (index < 0 || index >= this.size) {
        return -1;
      }
      let curNode = this.getNode(index);
      return curNode.val;
    }

    /** 判断链表是否为空，O(1) */
    get isEmpty(): boolean {
      return this.size === 0;
    }

    /** 链表中元素数量；O(1)  */
    get length(): number {
      return this.size;
    }

    /** 在链表的第一个元素之前添加一个值为 val的节点。插入后，新节点将成为链表的第一个节点。
     * O(1)
     * @param val
     */
    addAtHead(val: number): void {
      let node: ListNode = new ListNode(val, this.head);
      this.head = node;
      if (!this.tail) {
        this.tail = node;
      }
      this.size++;
    }

    /** 将值为 val 的节点追加到链表的最后一个元素。
     * O(1)
     * @param val
     */
    addAtTail(val: number): void {
      let node: ListNode = new ListNode(val, null);
      if (this.tail) {
        this.tail.next = node;
      } else {
        // 还没有尾节点，说明一个节点都还没有
        this.head = node;
      }
      this.tail = node;
      this.size++;
    }

    /** 在链表中的第 index个节点之前添加值为 val的节点。
     * 如果 index等于链表的长度，则该节点将附加到链表的末尾。
     * 如果 index大于链表长度，则不会插入节点。
     * 如果 index小于0，则在头部插入节点。
     * O(index)
     * @param index 索引值
     * @param val
     * @returns
     */
    addAtIndex(index: number, val: number): void {
      if (index === this.size) {
        this.addAtTail(val);
        return;
      }
      if (index > this.size) {
        return;
      }
      // <= 0 的情况都是在头部插入
      if (index <= 0) {
        this.addAtHead(val);
        return;
      }
      // 正常情况
      // 获取插入位置的前一个 node
      let curNode = this.getNode(index - 1);
      let node: ListNode = new ListNode(val, curNode.next);
      curNode.next = node;
      this.size++;
    }

    /** 如果索引 index有效，则删除链表中的第 index个节点。
     * O(index)
     * @param index
     * @returns
     */
    deleteElement(node: ListNode): void;
    deleteElement(index: number): void;
    deleteElement(param: number | ListNode): void {
      if (typeof param == "number") {
        if (param < 0 || param >= this.size) {
          return;
        }
        // 处理头节点
        if (param === 0) {
          this.head = this.head!.next;
          // 如果链表中只有一个元素，删除头节点后，需要处理尾节点
          if (param === this.size - 1) {
            this.tail = null;
          }
          this.size--;
          return;
        }
        // 索引有效
        let curNode: ListNode = this.getNode(param - 1);
        curNode.next = curNode.next!.next;
        // 处理尾节点
        if (param === this.size - 1) {
          this.tail = curNode;
        }
        this.size--;
      } else {
        param.val = param.next?.val!;
        param.next = param.next?.next!;
      }
    }

    /**清空
     * O(1)
     */
    clear() {
      this.head = null;
      this.tail = null;
      this.size = 0;
    }

    /** 根据值获取链表中所在的位置
     * O(n)
     * @param val 链表中的值获取所在的位置
     * @returns
     */
    locate(val: number) {
      let temp = this.head;
      if (temp == null) {
        return -1;
      } else {
        let index = 0;
        while (true) {
          if (temp.val === val) {
            return index;
          } else {
            if (temp.next != null) {
              temp = temp.next;
              index++;
            } else {
              break;
            }
          }
        }
        return -1;
      }
    }

    /** 反转链表
     * 双指针法;
     * O(n)
     * @param head
     * @returns
     */
    reverseList(head: ListNode | null): ListNode | null {
      let preNode: ListNode | null = null,
        curNode: ListNode | null = head,
        tempNode: ListNode | null;
      while (curNode) {
        tempNode = curNode.next;
        curNode.next = preNode;
        preNode = curNode;
        curNode = tempNode;
      }
      return preNode;
    }

    /** 链表相交
     *
     * @param headA
     * @param headB
     * @returns
     */
    static getIntersectionNode(
      headA: ListNode | null,
      headB: ListNode | null
    ): ListNode | null {
      let sizeA: number = 0,
        sizeB: number = 0;
      let curA: ListNode | null = headA,
        curB: ListNode | null = headB;
      while (curA) {
        sizeA++;
        curA = curA.next;
      }
      while (curB) {
        sizeB++;
        curB = curB.next;
      }
      curA = headA;
      curB = headB;
      if (sizeA < sizeB) {
        [sizeA, sizeB] = [sizeB, sizeA];
        [curA, curB] = [curB, curA];
      }
      let gap = sizeA - sizeB;
      while (gap-- && curA) {
        curA = curA.next;
      }
      while (curA && curB) {
        if (curA === curB) {
          return curA;
        }
        curA = curA.next;
        curB = curB.next;
      }
      return null;
    }

    /** 环形链表II
     * 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
     * @param head
     * @returns
     */
    static detectCycle(head: ListNode | null): ListNode | null {
      let slowNode: ListNode | null = head,
        fastNode: ListNode | null = head;
      while (fastNode !== null && fastNode.next !== null) {
        slowNode = slowNode!.next;
        fastNode = fastNode.next.next;
        if (slowNode === fastNode) {
          slowNode = head;
          while (slowNode !== fastNode) {
            slowNode = slowNode!.next;
            fastNode = fastNode!.next;
          }
          return slowNode;
        }
      }
      return null;
    }

    /** 获取指定 Node节点
     * O(index)
     * @param index 索引值
     * @returns
     */
    getNode(index: number): ListNode {
      let curNode: ListNode = new ListNode(0, this.head);
      for (let i = 0; i <= index; i++) {
        curNode = curNode.next!;
      }
      return curNode;
    }

    toString(): string {
      return this.head?.val + " ->...-> " + this.tail?.val;
    }
  }
}
